package com.dragon.datastructure.recursion;

/**
 * 数组求和
 * Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1])
 * Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1])
 * Sum(arr[n-1...n-1]) = arr[n - 1] + Sum(arr[])
 * <p>
 * 注意递归函数的宏观语意
 * 递归函数就是一个函数，完成一个功能
 *
 * @author dragon
 * @since 2019/12/30
 */
public class ArraySum {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println(sum(array));
    }

    /**
     * 求数组的和
     *
     * @param array
     * @return
     */
    public static int sum(int[] array) {
        return sum(array, 0);
    }

    /**
     * 计算arr[l...n]这个区间所有数字的和
     *
     * @param array 数组
     * @param l     从索引l开始
     * @return 返回累加的和
     */
    private static int sum(int[] array, int l) {
        // 求解最基本的问题
        if (l == array.length) {
            return 0;
        }

        // 把原问题转换为更小的问题
        return array[l] + sum(array, l + 1);
    }
}
